package leetcode.L148;

import java.util.Comparator;
import java.util.PriorityQueue;

class ListNode {
    int val;
    ListNode next;
    ListNode() {}
    ListNode(int val) { this.val = val; }
    ListNode(int val, ListNode next) { this.val = val; this.next = next; }
}
public class Solution {
    public ListNode sortList(ListNode head) {
        //找到逆序的，然后遍历到lastSorted,找地方插入
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0, head);
        ListNode lastSorted = dummy.next;
        ListNode prev = head;
        ListNode findInsPrev = dummy;
        ListNode tmp = dummy;
        while (prev.next != null) {
            if (prev.next.val<prev.val) {
                //寻找插入节点
                findInsPrev=dummy;
                while (findInsPrev.next!=null&&findInsPrev!=lastSorted) {
                    if (findInsPrev.next.val>prev.next.val) {
                        break;
                    }
                    findInsPrev = findInsPrev.next;
                }
                tmp = prev.next;
                prev.next=tmp.next;
                tmp.next=findInsPrev.next;
                findInsPrev.next=tmp;
            }
        }
        return dummy.next;
    }

    public ListNode sortList1(ListNode head) {
        //找到逆序的，然后遍历到lastSorted,找地方插入
        if (head == null) {
            return null;
        }
        ListNode dummy = new ListNode(0, null);
        PriorityQueue<ListNode> pq = new PriorityQueue<ListNode>(new Comparator<ListNode>() {
            @Override
            public int compare(ListNode o1, ListNode o2) {
                return o1.val-o2.val;
            }
        });
        while (head != null) {
            pq.add(head);
            head = head.next;
        }
        ListNode curr = null;
        ListNode prev = dummy;
        while (!pq.isEmpty()) {
            curr = pq.poll();
            prev.next = curr;
            prev = curr;
        }
        curr.next = null;
        return dummy.next;
    }

    public static void main(String[] args) {
        ListNode s4=new ListNode(3,null);
        ListNode s3=new ListNode(1,s4);
        ListNode s2=new ListNode(2,s3);
        ListNode s1=new ListNode(4,s2);
        Solution solution = new Solution();
        solution.sortList(s1);

    }
}